软考真题
第4题
【说明】
计算两个字符串x和y的最长公共子串(Longest Common Substring)。

假设字符串x和字符串y的长度分别为m和n,用数组c的元素c[i][j]记录x中前i个字符和y中前j个字符的最长公共子串的长度。

c[i][j]满足最优子结构,其递归定义为:



计算所有c[i][j](0≤i≤m,0≤j≤n)的值,值最大的c[i][j]即为字符串x和y的最长公共子串的长度。根据该长度即i和j,确定一个最长公共子串。

(1) 常量和变量说明

x,y:长度分别为m和n的字符串。

c[i][j]:记录x中前i字符和y中前j个字符的最长公共子串的长度。

max:x和y的最长公共子串的长度。

maxi,maxj:分别表示x和y的某个最长公共子串的最后一个字符在x和y中的位置(序号)。

(2) C程序







【问题:4.1】根据以上说明和C代码,填充C代码中的空(1)~(4)。
【问题:4.2】根据题干说明和以上C代码,算法采用了(5)设计策略。
分析时间复杂度为(6)(用O符号表示)。
【问题:4.3】根据题干说明和以上C代码,输入字符串x="ABCADAB’,'y="BDCABA",则输出为(7)。
2015年 下半年 下午试卷 案例
正确答案:
你的答案:
请先在App中激活(应用市场搜“软考真题”)
知识点:
试卷:
2015年 下半年 下午试卷 案例

笔记

请先在App中激活(应用市场搜“软考真题”)

2019-10-26


请先在App中激活(应用市场搜“软考真题”)

2019-10-12


请先在App中激活(应用市场搜“软考真题”)

2019-10-27


请先在App中激活(应用市场搜“软考真题”)

2019-11-06


失之定归

请先在App中激活(应用市场搜“软考真题”)

2020-04-18


李建雄

请先在App中激活(应用市场搜“软考真题”)

2020-10-29


答题卡
加油
纠错
得分:0